Communications networks use a communications medium to transmit information in the form of computer data, voice, music, video, etc., between users or between users and service providers. The communications medium may be a wire link, a fiber optic link, or a wireless link. The wireless link may include, but is not limited to, radio frequency, infrared, laser light, and microwave. The network may, in fact, use a combination of different communications links. With the exception of a small number of networks that use dedicated communications links between each user, most information networks use a shared communications medium to carry the transmitted information. Examples of information networks using a shared communications medium include: Ethernet, token ring, and wireless Ethernet (IEEE 802.11).
In networks that use a shared communications medium, access to the shared medium must be controlled to prevent a situation where a subset of users are able to dominate the medium and block other users from using the medium. Another situation that also must be prevented is that too many users attempt to transmit information simultaneously, leading to no user being able to successfully transmit any information at all because of information packets colliding with one another all over the network.
Some networks, such as Ethernet, do not prevent these situations. A user on an Ethernet network is free to transmit as much information (in the form of data packets) as fast and as soon as he is able to produce it as long as the medium is sensed to be idle. If a collision between two or more data packets from multiple users occurs, then a backoff mechanism comes into play permitting colliding users to recover from the collision and to reduce the probability of future collisions from occurring. This data anarchy works well in a network with a low to medium number of users, but latency and throughput performance degrades quite ungracefully as the number of users increases.
In a token ring network, a user can transmit data only if the user is in possession of a “token”. The token is a special control packet that is transferred from one user to the next in a circular fashion, hence the name token ring. Whoever is in possession of the token is in control of the medium and can transmit data freely. However, token ring networks may be inefficient because users that have no data to transmit will still obtain the token and therefore waste valuable network bandwidth, while users with large amounts of data to transmit must wait for the token to make its way around the network before they can resume transmitting data.
In wireless Ethernet (IEEE 802.11), two types of medium sharing are provided. In a first type of medium sharing, called contention access, a user is free to transmit data if the user detects that the medium has been idle for a sufficient period of time. A second type of media sharing, called contention-free access, a centralized controller controls access to the medium. A user can only transmit data after it has been polled by the centralized controller. During contention-free access, the network behaves in a manner that is similar to a token ring network, and while during the contention period, the network behaves similarly to Ethernet. And in essence, wireless Ethernet combines features of both Ethernet and token ring networks.
In IEEE 802.11, the network designers are required to implement the contention access method but not necessarily the contention-free access method, since the former is specified to be mandatory and the latter is optional. According to the mandatory method, when a station has information to transmit, it checks the medium (for IEEE 802.11 in the United States, the medium spectrum are in the 2.4 and 5.2 GHz industrial-scientific-medical (ISM) frequency bands) to see if the medium is idle. The designers have defined two different states of idle. The first state of idle is known as “physical idle” and it is when there are no actual transmissions being performed on the medium. The second state of idle is known as “virtual idle” and it is when there are no anticipated transmissions from users in the network. Both states of idle must be met for the medium to be considered idle.
Prior to a new transmission, the user selects a random backoff time from an interval [0, CW), which includes 0 but excludes CW, where CW=CWmin+1 for a new transmission and CWmin is a predetermined value that is specified in the technical specifications. The interval is commonly referred to as a contention window. This randomly selected backoff time is placed into a backoff timer that begins decrementing after the medium is determined to have been idle for a DIFS interval, where DIFS is also a predetermined value defined in the standard. However, the backoff timer only decrements when the medium remains idle (both states of idle). If the medium is no longer idle, then the backoff timer stops decrementing; the backoff timer resumes decrementing after the medium has become idle for a DIFS.
Once the backoff timer reaches zero, the user transmits a frame. If a collision occurs, the user selects a new random backoff time from a contention window that is twice as large as the previous contention window, [0, 2*CW). After the backoff timer expires with the new backoff time, the user will transmit the same frame again. If the transmission fails yet again, the user selects another random backoff time from a contention window that is twice as large as the previous contention window, [0, 4*CW). When the contention window reaches a maximum range [0, CWmax], including both 0 and CWmax, where CWmax is yet another predetermined value specified in IEEE 802.11, the contention window will no longer increase in size, regardless of the occurrence of any future collisions of the frame. This backoff process is known as truncated binary exponential backoff and continues until the transmission is successful. The frame may be dropped if it reaches a retry limit or a maximum lifetime, which are values also defined by the IEEE 802.11 standard. After the frame is successfully transmitted or after the frame is dropped, the user will perform a new backoff chosen from the initial contention window [0, CW), with CW=CWmin+1, in preparation for the transmission of another new frame.
A disadvantage of the truncated binary exponential backoff process for contention access is that it does not differentiate the current load on the network, e.g., it always doubles the contention window whether there are two or more users colliding with one another. The truncated binary exponential backoff process is not adaptive to the network condition. By not being adaptive, the truncated binary exponential backoff process operates in the same way, regardless of network load and condition. This may result in a user having to wait an inordinate amount of time in a lightly loaded network when there are ample opportunities to transmit. Another disadvantage of the truncated binary exponential backoff process is its poor throughput and latency performance with increased contention, due to each user with data to transmit automatically being required to use the same truncated binary exponential backoff process for a new or retry transmission.
A need has therefore arisen for an adaptive methodology for providing optimal control of contention access to a shared medium in response to network load changes.